package doublepointer;

/**
 * @Classname : LongestSubstringWithAtMostKDistinctCharacters
 * @Description : <a href="https://leetcode.cn/problems/longest-substring-with-at-most-k-distinct-characters/">340. 至多包含 K 个不同字符的最长子串</a>
 * @Author : chentianyu
 * @Date 2023/2/23 23:54
 */


public class LongestSubstringWithAtMostKDistinctCharacters {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int[] chars = new int[128];
        int l = 0, r = 0, max = 0, cnt = 0;
        for (; r<s.length(); r++) {
            if (chars[s.charAt(r)]++ == 0)
                cnt++;
            if (cnt == k && r - l + 1 > max)
                max = r - l + 1;
            while (cnt > k) {
                if (--chars[s.charAt(l++)] == 0)
                    cnt--;
            }
        }
        return max >= k ? max : s.length();
    }
}
